Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions

摘要

In this two-part paper, we consider SDL constructions of optical queues witha limited number of recirculations through the optical switches and the fiberdelay lines. We show that the constructions of certain types of optical queues,including linear compressors, linear decompressors, and 2-to-1 FIFOmultiplexers, under a simple packet routing scheme and under the constraint ofa limited number of recirculations can be transformed into equivalent integerrepresentation problems under a corresponding constraint. Given $M$ and $k$,the problem of finding an \emph{optimal} construction, in the sense ofmaximizing the maximum delay (resp., buffer size), among our constructions oflinear compressors/decompressors (resp., 2-to-1 FIFO multiplexers) isequivalent to the problem of finding an optimal sequence ${\dbf^*}_1^M$ in$\Acal_M$ (resp., $\Bcal_M$) such that $B({\dbf^*}_1^M;k)=\max_{\dbf_1^M\in\Acal_M}B(\dbf_1^M;k)$ (resp., $B({\dbf^*}_1^M;k)=\max_{\dbf_1^M\in\Bcal_M}B(\dbf_1^M;k)$), where $\Acal_M$ (resp., $\Bcal_M$) is the set of allsequences of fiber delays allowed in our constructions of linearcompressors/decompressors (resp., 2-to-1 FIFO multiplexers). In Part I, wepropose a class of \emph{greedy} constructions of linearcompressors/decompressors and 2-to-1 FIFO multiplexers by specifying a class$\Gcal_{M,k}$ of sequences such that $\Gcal_{M,k}\subseteq \Bcal_M\subseteq\Acal_M$ and each sequence in $\Gcal_{M,k}$ is obtained recursively in a greedymanner. We then show that every optimal construction must be a greedyconstruction. In Part II, we further show that there are at most two optimalconstructions and give a simple algorithm to obtain the optimalconstruction(s).